
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include "./seqstackqueue.h"

// 运算符优先级判断
int priority(char op);

void infixToSuffix(Queue *Q)
{
    Stack *S = createStack(100);
    push(S, '#'); // 栈底元素

    char c, t;
    do
    {
        c = getchar();
        switch (c)
        {
        case ' ':
            break;
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            enqueue(Q, c); // 数值进入队列
            break;
        case '(':
            push(S, c); // 左括号进栈
            break;
        case ')':
        case '#':
            // 右括号 或 # 出栈
            do
            {
                // 当左括号或者 # 号时，出栈
                t = pop(S);
                // 若出栈的值不是 左括号 并且 也不是井号，则将该值进入队列
                if (t != '(' && t != '#')
                {
                    enqueue(Q, t);
                }
                // 若出栈的值不是 左括号 或者 不是栈底 则继续出栈
            } while (t != '(' && S->top != -1);

            break;
        case '+':
        case '-':
        case '*':
        case '/':
            // 若当前运算符优先级 小于等于 栈顶运算符的优先级， 则出栈并进入队列
            // char p =  '0' + peek(S); // BUG: 编译报错，必须放到循环外，且 peek 后有问题
            // printf("------------>cur=%c , stack top: %c\n", c, p);
            // while (priority(c) <= priority(p))
            while (priority(c) <= priority(peek(S)))
            {
                t = pop(S);
                enqueue(Q, t);
            }
            // 若是运算符则入栈
            push(S, c);
            break;
        default:
            break;
        }

    } while (c != '#');
}

// 后缀表达式计算
int suffixExprCaculate(Queue *Q)
{
    Stack *S = createStack(100);

    char ch;
    int x, y;
    while (!(queueEmpty(Q)))
    {
        ch = dequeue(Q);
        // 当出队列的是数字时则进栈， 是运算符则出栈进行计算
        if (ch >= '0' && ch <= '9')
        {
            // 转换为 int 类型 ch - '0'
            int value = ch - '0';
            push(S, value);
        }
        else
        {
            y = pop(S);
            x = pop(S);

            switch (ch)
            {
            case '+':
                push(S, x + y);
                break;
            case '-':
                push(S, x - y);
                break;
            case '*':
                push(S, x * y);
                break;
            case '/':
                push(S, x / y);
                break;
            }
        }
    }

    return peek(S);
}

int main()
{
    //   9-(2+4*7)/5+3#
    Queue *infix = create(100);
    infixToSuffix(infix);

    printf("----------seqstack pop-------------\n");
    while (!queueEmpty(infix))
    {
        dequeue(infix);
    }

    exit(0);
    Queue *exprQ = create(100);
    char *expression = "9247*+5/-3+";
    for (size_t i = 0; i < strlen(expression); i++)
    {
        enqueue(exprQ, expression[i]);
    }
    printf("---------------start caculate expression values--------------\n");
    printf("======> %d\n", suffixExprCaculate(exprQ));

    return 0;
}

int priority(char op)
{
    switch (op)
    {
    case '(':
    case '#':
        return 0;
    case '-':
    case '+':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return -1;
    }
}